Search for: All records

Abstract We presentSprout, the first sound and complete implementability checker for symbolic multiparty protocols.Sproutsupports protocols with dependent refinements on message values, loop memory, and multiparty communication with generalized, sender-driven choice.Sproutchecks implementability via an optimized, sound and complete reduction to the fixpoint logic$$\mu $$ $\mu$CLP, and usesMuValas a backend solver for$$\mu $$ $\mu$CLP instances. We evaluateSprouton an extended benchmark suite of implementable and non-implementable examples, and show thatSproutoutperforms its competititors in terms of expressivity and precision, and provides competitive runtime performance.Sproutadditionally provides support for verifying custom functional correctness properties beyond implementability. 

We study the implementability problem for an expressive class of symbolic communication protocols involving multiple participants. Our symbolic protocols describe infinite states and data values using dependent refinement predicates. Implementability asks whether a global protocol specification admits a distributed, asynchronous implementation, namely one for each participant, that is deadlock-free and exhibits the same behavior as the specification. We provide a unified explanation of seemingly disparate sources of non-implementability through a precise semantic characterization of implementability for infinite protocols. Our characterization reduces the problem of implementability to (co)reachability in the global protocol restricted to each participant. This compositional reduction yields the first sound and relatively complete algorithm for checking implementability of symbolic protocols. We use our characterization to show that for finite protocols, implementability is co-NP-complete for explicit representations and PSPACE-complete for symbolic representations. The finite, explicit fragment subsumes a previously studied fragment of multiparty session types for which our characterization yields a co-NP decision procedure, tightening a prior PSPACE upper bound. 

Multiparty session types (MSTs) are a type-based approach to verifying communication protocols, represented as global types in the framework. We present a precise subtyping relation for asynchronous MSTs with communicating state machines (CSMs) as implementation model. We address two problems: when can a local implementation safely substitute another, and when does an arbitrary CSM implement a global type? We define safety with respect to a given global type, in terms of subprotocol fidelity and deadlock freedom. Our implementation model subsumes existing work which considers local types with restricted choice. We exploit the connection between MST subtyping and refinement to formulate concise conditions that are directly checkable on the candidate implementations, and use them to show that both problems are decidable in polynomial time.